package tree;

import java.lang.management.MemoryNotificationInfo;
import java.util.LinkedList;
import java.util.Queue;

//二叉树的直径
public class leetcode543 {
    public static void main(String[] args) {
//        Integer[] nums = {1,2,3,4,5};
        Integer[] nums = {4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2};
        TreeNode root = createTree(nums);
        System.out.println(diameterOfBinaryTree(root));
    }

    public static TreeNode createTree(Integer[] nums){
        if(nums == null || nums.length == 0) return null;

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while(!queue.isEmpty() && i < nums.length){
            TreeNode curr = queue.poll();

            if(i<nums.length && nums[i] != null){
                curr.left = new TreeNode(nums[i]);
                queue.offer(curr.left);
            }
            i++;
            if(i<nums.length && nums[i] != null){
                curr.right = new TreeNode(nums[i]);
                queue.offer(curr.right);
            }
            i++;
        }
        return root;
    }

    public static int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 0;
//        if(root.left == null || root.right == null) return 1;
        return Math.max(2 + MaxDepth(root.left) + MaxDepth(root.right), Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
    }

    public static int MaxDepth(TreeNode root){
        if(root == null) return -1;
        return  1+Math.max(MaxDepth(root.left), MaxDepth(root.right));
    }
}
